//0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
// 
//
// 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 
//
// 
//
// 示例 1： 
//
// 
//输入: n = 5, m = 3
//输出: 3
// 
//
// 示例 2： 
//
// 
//输入: n = 10, m = 17
//输出: 2
// 
//
// 
//
// 限制： 
//
// 
// 1 <= n <= 10^5 
// 1 <= m <= 10^6 
// 
//
// Related Topics 递归 数学 👍 711 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

/*
数学+迭代 (约瑟夫环)

对于[n, m问题]，首轮删除环中第m个数字后，得到一个长度为 n - 1 的数字环。
由于有可能 m > n，因此删除的数字为 (m - 1) % n，删除后的数字环从下个数字(即m % n)开始，
设 t = m % n，可得"新数字环"在"旧数字环"中的对应下标为: 【 t，t+1，t+2，...，0，1，...，t-3，t- 2 】（t-1为被删除的数字）

旧环删除数字nums[(m-1)%n]后的新环的起始下标为 旧环中的 m % n = t
删除一轮后的数字环变为[n-1，m问题]，其数字下标对应关系如下:
	      新环下标(本环)    新环下标在旧环(上环)下标中对应的下标
			   0                      (t+0)%n
			   1                      (t+1)%n
			  ...                      ...
			  n-2                     (t+n-2)%n

所以新环中的下标 x 与在旧环中对应下标 X 的关系为 X = (t + x) % n
删除到最后的新环中只有一个元素，下标为0，可以通过下标递推关系 找出其在"最旧环"中的下标!

 X = (t + x) % n   --->  f(X) = (t + f(X - 1)) % n         (f(X - 1)为旧环下标，f(X)为旧环在其"上一层"新环中对应的下标)
                   --->       = (m % n + f(X - 1)) % n
                   --->       = (m + f(X - 1)) % n         (m % n % n == m % n)

最终的环，只有一个元素，下标为 0
推导最终环的上一个环，有两个元素......
再到上一个环，有三个元素，直到推到最原始的 n 个元素的环
*/
class Solution {
    public int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
